package chapter02;

import org.w3c.dom.Node;

public class IsValidBST98 {
    /**
     * 树形dp
     * 假设当前节点x 可以寻求左子树最大值和右子树最小值以及左右子树是否是BST信息
     * 因此递归函数可以返回 最小值 最大值 isBST 将三个变量封装在一个类中 返回类
     * 递归出口
     * 1).x==null
     *    return null
     * 2).找子树最大值 最小值
     *    min=x.value
     *    max=x.value
     *    isBST=false
     *    leftInfo=process(x.left)
     *    rightInfo=process(x.right)
     *    min=Math.min(min,leftInfo.min,rightInfo.min)
     *    max=Math.max(max,leftInfo.max,rightInfo.max)
     *    更新isBST 左右子树是BST并且左子树最大值小于x.value 右子树最小值大于x.value
     *    (leftInfo==null||leftInfo.isBST&&leftInfo.max<x.val)&&(rightInfo==null|| rightInfo.isBST&&rightInfo.min>x.val)
     *      isBST=true
     *   return new Info(isBST,min,max)
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public class Info{
        public boolean isBST;
        public int min;
        public int max;

        public Info(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        return process(root).isBST;
    }

    public Info process(TreeNode x){
        if(x==null){
            return null;
        }
        int min=x.val;
        int max=x.val;
        boolean isBST=false;
        Info leftInfo=process(x.left);
        Info rightInfo=process(x.right);
        if(leftInfo!=null){
            min=Math.min(min, leftInfo.min);
            max=Math.max(max, leftInfo.max);
        }
        if(rightInfo!=null){
            min=Math.min(min, rightInfo.min);
            max=Math.max(max, rightInfo.max);
        }
        if((leftInfo==null||leftInfo.isBST&&leftInfo.max<x.val)&&(rightInfo==null|| rightInfo.isBST&&rightInfo.min>x.val)){
            isBST=true;
        }
        return new Info(isBST,min,max);
    }
}
